Оптимизација коришћењем динамичког програмирања
Динамичко програмирање се често примењује у решавању оптимизационих задатака (задатака у којима се тражи да се одреди најмања или највећа вредност која задовољава неки услов). Да би оптимизациони задатак могао да се решава динамичким програмирањем, потребно је формулисати његово рекурзивно решење, што значи да проблем мора да задовољава такозвано својство оптималне подструктуре. То значи да се оптимално решење полазног проблема може одредити на основу оптималних решења потпроблема истог облика, али мање димензије.
На пример, најкраћи пут измећу тачке \(A\) и тачке \(B\) који пролази преко тачке \(C\) се добија тако што се искомбинују најкраћи пут између тачке \(A\) и тачке \(C\) и накраћи пут између тачке \(C\) и тачке \(B\), што значи да проблем одређивања најкраћих путева има својство оптималне подструктуре и може се решавати динамичким програмирањем (на тој техници је заснован Дајкстрин алгоритам, који је један од најчувенијих алгоритама за решвање тог проблема).
Међутим, најјефтинији авионски лет од аеродрома \(A\) до аеродрома \(B\) преко аеродрома \(C\) не мора да буде комбинација најјефтинијих летова од \(A\) до \(C\) и од \(C\) до \(B\) (због посебних попуста које авио-компаније нуде за повезане летове), тако да се проблем одређивања најјефтинијег лета нема својство оптималне подструктуре и не може се решавати динамичким програмирањем.